package Leetcode.lc105;

import Leetcode.tools.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Sloution {
    Map<Integer,Integer> map=new HashMap<>();
    //中序节点存储索引，便于切割
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTrees(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    private TreeNode buildTrees(int[] preorder, int startPre, int length, int[] inorder, int startIn, int length1) {
        if(startIn>=length1 || startPre>=length) return null;
        //获得中序节点
        Integer rootindex = map.get(preorder[0]);
        TreeNode node = new TreeNode(inorder[rootindex]);
        int cutlength=rootindex-startIn;
        //切割前序数组
        node.left=buildTrees(preorder,startPre+1,startPre+cutlength+1,inorder,startIn,rootindex);
        node.right=buildTrees(preorder,startPre+cutlength+1,length,inorder,rootindex+1,length1);
       return node;
    }
}
